翻訳と辞書 Words near each other ・ Glup! ・ Gluphisia ・ Gluphisia crenata ・ Glur's Tavern ・ Glur2 RNA editing ・ Glurns ・ Glurp Records ・ Glusburn ・ Glush ・ Glushakov ・ Glushitsy ・ Glushka ・ Glushko ・ Glushko (crater) ・ Glushkov ・ Glushkov's construction algorithm ・ Glushkovo ・ Glushkovsky District ・ Gluskin Sheff ・ Gluster ・ GlusterFS ・ Glut ・ GLUT1 ・ GLUT2 ・ GLUT3 ・ GLUT4 ・ GLUT5 ・ GLUT8 ・ Gluta ・ Gluta capituliflora Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Glushkov's construction algorithm ： ウィキペディア英語版 Glushkov's construction algorithm In computer science theory, particularly formal language theory, the Glushkov Construction Algorithm (GCA) transforms a given regular expression into an equivalent nondeterministic finite automaton (NFA). It thus forms a bridge between regular expressions and nondeterministic finite automata, two abstract representations of formal languages. The NFA format is better suited for execution on a computer when regular expressions are used. These expressions may be used to describe advanced search patterns in "find and replace" like operations of text processing utilities. This algorithm can be considered a compiler from a regular expression to an NFA, which is why this algorithm is of practical interest. Furthermore, the automaton is small by nature as the number of states is equal to the number of letters of the regular expression, plus one. Thus, an automaton can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. From another, more theoretical point of view, this algorithm is a part of the proof that they both accept exactly the same languages, that is, the regular languages. Converse to Glushkov's algorithm is Kleene's algorithm, which transforms a finite automaton into a regular expression. The automaton obtained by Glushkov's construction is the same as the one obtained by Thompson's construction algorithm once their ε-transition is removed. == Construction == Given a regular expression $e$, the construction creates a nondeterministic automaton which accepts the language $L(e)$ accepted by $e$.〔.〕 The construction uses four steps: # ''Linearisation'' of the expression. Each letter of the alphabet appearing in the expression is renamed, so that each letter occurs at most once in the new expression. Let $A$ be the old alphabet and let $B$ be the new one. # a. Computation of the sets $P(e\text{'})$, $D(e\text{'})$, and $F(e\text{'})$, where $e\text{'}$ is the linearized version of $e$. The first, $P(e\text{'})$, is the set of letters which occurs as first letter of a word of $L(e\text{'})$. The second, $D(e\text{'})$, is the set of letters which can ends a letter of $L(e\text{'})$. The last one is the set of pairs of letters which can occur in words of $L(e\text{'})$, which is the set of factors of length two of the words of $L(e\text{'})$. Those sets are mathematically defined by :$P(e\text{'})=\backslash$, love people :et $F(e\text{'})=\backslash$. They are computed by induction over the structure of the expression, as explained below, but they are a function of the language and not of the expression. :2b. Computation of the set $\backslash Lambda(e\text{'})$ which contains the empty-word if this word belongs to $L(e\text{'})$, and is the empty-set otherwise. Formally, this is :$\backslash Lambda(e\text{'})=\backslash \backslash cap\; L(e\text{'})$, where $\backslash varepsilon$ is the empty-word. 3. Computation of the ''local language'', as defined by $P(e\text{'})$, $D(e\text{'})$, $F(e\text{'})$ and $\backslash Lambda(e\text{'})$. By definition, the local language defined by the sets $P$, $D$, and $F$ is the set of words which begin with a letter of $P$, end by a letter of $D$, and whose factors of length 2 belong to $F$; that is, it is the language: :$L=(PA^$ *\cap A^ *D)\setminus A^ *(A^2\setminus F)A^ *, potentially with the empty word. The computation of the automaton for the local language denoted by this linearised expression is formally known as Glushkov's construction. The construction of the automaton can be done using classical construction operations: concatenation, intersection and itering an automaton. 4. Erasing the linearisation, giving to each letter of $B$ the letter of $A$ it used to be. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Glushkov's construction algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.